/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item10;

import org.junit.Test;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:JumpFloorII.java v1.0 2018/8/12 上午12:57 LvJing Exp $
 */
public class JumpFloorII {

    /**
     * 题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
     * 思路：一共1级台阶，有1种跳法；一共2级，第一次跳1级后面有f(2-1)，第一次跳2级后面有f(2-2)，也就是f(2-1)+f(2-2)种跳法，
     * 跳n级，就是f(0) + f(1) + f(2) + ... + f(n-1)种跳法 f(n-1) = f(0)+f(1)+...f(n-2)，所以f(n)=f(n-1)+f(n-1)
     */
    public class Solution {
        public int JumpFloorII(int target) {
            if (target <= 0)
                return -1;
            if (target == 1)
                return 1;
            return 2 * JumpFloorII(target - 1);
        }
    }

    @Test
    public void test01() {
        System.out.println(new Solution().JumpFloorII(30));
    }
}
